package com.kjc.demo.basic.test;

import java.util.ArrayList;
import java.util.List;
 
public class Tree {
 
	private Node root;
	private List<Node> list = new ArrayList<Node>();
	public Tree(){
		init();
	}
	
	//定义节点类，内部类
	public class Node {
 
		private String data;
		private Node lchild;//定义指向左子树的指针
		private Node rchild;//定义指向右子树的指针
		public Node(String data, Node lchild,Node rchild){
			this.data = data;
			this.lchild = lchild;
			this.rchild = rchild;
		}
	}
	//树的初始化；先从叶子节点开始，由叶到根
	public void init(){
		Node x = new Node("X",null,null);
		Node y = new Node("y",null,null);
		Node d = new Node("d",x,y);
		Node e = new Node("e",null,null);
		Node f = new Node("f",null,null);
		Node c = new Node("c",e,f);
		Node b = new Node("b",d,null);
		Node a = new Node("a",b,c);
		root = a;
	}
	
	/*
	 * 对该二叉树进行前序遍历， 结果存储到list中，前序遍历：
	 * */
	public void preOrder(Node node){
		//存储根节点
		list.add(node);
		//如果左子树不为空继续往左找，在递归调用方法的时候一直会
		//将子树的根存入list，这就做到了先遍历根节点
		if(node.lchild !=null){
			preOrder(node.lchild);
		}
		//无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树
		//上遍历，保证了根左右的遍历顺序
		if(node.rchild!=null){
			preOrder(node.rchild);
		}
	}
	/*
	 * 对该二叉树进行中序遍历，结果存储到list中
	 * */
	public void inOrder(Node node){
		if(node.lchild !=null){
			preOrder(node.lchild);
		}
		list.add(node);
		if(node.rchild!=null){
			preOrder(node.rchild);
		}
	}
	
	/*
	 *对该二叉树进行后序遍历，结果存储到list中
	 * */
	public void postOrder(Node node){
		if(node.lchild!=null){
			postOrder(node.lchild);
		}
		if(node.rchild!=null){
			postOrder(node.rchild);
		}
		list.add(node);
	}
	/*
	 * 返回当前树的深度
	 * 说明:
      *  1、如果一棵树只有一个结点，它的深度为1。
      *  2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1；
      *  3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1；
      *  4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。
      *  
      *  */
	public int getTreeDepth(Node node){
		if(node.lchild ==null && node.rchild==null){
			return 1;
		}
		int left=0, right=0;
		if(node.lchild!=null){
			left = getTreeDepth(node.lchild);
		}
		if(node.rchild!=null){
			right = getTreeDepth(node.rchild);
		}
		return left>right?left+1:right+1;
	}
	//得到遍历结果
	public List<Node> getResult(){
		return list;
	}
	public static void main(String[] args){
		Tree tree = new Tree();
		System.out.println("根节点是:"+tree.root);
//		tree.preOrder(tree.root);
		tree.postOrder(tree.root);
//		tree.inOrder(tree.root);
		for(Node node:tree.getResult()){
			System.out.print(node.data);
		}
		System.out.println("树的深度是:"+tree.getTreeDepth(tree.root));
	}
}